package com.wc.data_structures.search;


import java.util.Arrays;

/**
 * @Author congge
 * @Date 2023/4/21 17:27
 * @description
 */
public class SearchUtil {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        SearchUtil searchUtil = new SearchUtil();
        System.out.println(searchUtil.fibonacciSearch(array, 10));
    }

    /**
     * 顺序查找
     *
     * @param array 待查找数组
     * @param num   待查数
     * @return 返回其在数组中的位置，没有返回-1
     */
    public int seqSearch(int[] array, int num) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分查找
     *
     * @param array 待查找数组
     * @param num   待查数
     * @return 返回其在数组中的位置，没有返回-1
     */
    public int binarySearch(int[] array, int num) {
        int left = 0;
        int right = array.length - 1;
        if (num < array[left] || num > array[right]) {
            return -1;
        }
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (array[mid] == num) {
                return mid;
            } else if (array[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找
     *
     * @param array 待查找数组
     * @param left  左边界
     * @param right 左边界
     * @param num   待查数
     * @return 返回其在数组中的位置，没有返回-1
     */
    public int binarySearch(int[] array, int left, int right, int num) {
        if (left > right) {
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (array[mid] == num) {
            return mid;
        } else if (array[mid] > num) {
            return binarySearch(array, left, mid - 1, num);
        } else {
            return binarySearch(array, mid + 1, right, num);
        }
    }

    /**
     * 差值查找
     * ｛1，2，3，4｝
     *
     * @param array 待查找数组
     * @param num   待查数
     * @return 返回其在数组中的位置，没有返回-1
     */
    public int insertValueSearch(int[] array, int num) {
        int left = 0;
        int right = array.length - 1;
        if (num < array[left] || num > array[right]) {
            return -1;
        }
        int mid;

        while (left <= right) {
            mid = left + (right - left) * (num - array[left]) / (array[right] - array[left]);
            if (array[mid] == num) {
                return mid;
            } else if (array[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 斐波那契查找
     * ｛1，2，3，4｝
     * 可能需要扩张数组长度
     *
     * @param array 待查找数组
     * @param num   待查数
     * @return 返回其在数组中的位置，没有返回-1
     */
    public int fibonacciSearch(int[] array, int num) {
        int left = 0;
        int right = array.length - 1;
        // 表示斐波那契数值的下标
        int k = 0;
        int mid;
        int[] f = getFibonacciList(array.length);
        // 找到最大的k
        while (f[k] - 1 < right) {
            k++;
        }
        int[] tmp = Arrays.copyOf(array, f[k]);
        // 将额外的数都填写为最大的数
        for (int i = right + 1; i < tmp.length; i++) {
            tmp[i] = array[right];
        }
        right = f[k];

        // 循环处理
        while (left <= right) {
            mid = left + f[k - 1] - 1;
            if (tmp[mid] == num) {
                return Math.min(mid, right);
            } else if (tmp[mid] > num) {
                right = mid - 1;
                k--;
            } else {
                left = mid + 1;
                k -= 2;
            }
        }
        return -1;
    }

    /**
     * 获得一个斐波那契数列
     *
     * @param n n长度的斐波
     * @return 返回序列
     */
    public int[] getFibonacciList(int n) {
        if (n <= 0) {
            return null;
        }
        int[] f = new int[n];
        f[0] = 1;
        if (n == 1) {
            return f;
        }
        f[1] = 1;
        for (int i = 2; i < n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

}
